package main

import "fmt"

/*
在行和列都有序的二维数组中，找num，返回true or false
*/

func search(arr [][]int, t int) bool {
	m := len(arr)
	n := len(arr[0])
	i, j := 0, n-1
	for {
		for {
			if arr[i][j] > t {
				j--
			} else if arr[i][j] < t {
				i++
			} else {
				return true
			}
			if i >= m || j < 0 {
				return false
			}
		}
	}
}

func main() {
	arr := [][]int{
		{1, 3, 5, 7, 8, 9, 10},
		{2, 4, 6, 8, 9, 10, 11},
		{3, 88, 89, 90, 92, 96, 99},
		{4, 89, 90, 91, 93, 99, 100},
	}
	fmt.Println(search(arr, 89))
}
